public class MinWindow {
    // 最小覆盖子串
    // https://www.nowcoder.com/practice/c466d480d20c4c7c9d322d12ca7955ac?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
    public String minWindow (String S, String T) {
        // write code here
        int[] hash1 = new int[58];
        int[] hash2 = new int[58];
        int type1 = 0;
        int type2 = 0;
        int leftIndex = -1;
        int rightIndex = -1;
        int minLength = 0x3f3f3f3f;
        for (char c : T.toCharArray()) {
            if (hash1[c-'A']++ == 0) {
                type1++;
            }
        }
        char[] ss = S.toCharArray();
        for (int left = 0, right = 0; right < ss.length; right++) {
            if (++hash2[ss[right]-'A'] <= hash1[ss[right]-'A']) {
                if (hash2[ss[right]-'A'] == hash1[ss[right]-'A']) {
                    type2++;
                }
            }
            while (type1 == type2 && left <= right) {
                if (hash2[ss[left]-'A']-- == hash1[ss[left]-'A']) {
                    type2--;
                }
                if (right-left+1 < minLength) {
                    minLength = right-left+1;
                    leftIndex = left;
                    rightIndex = right;
                }
                left++;
            }
        }
        return rightIndex == -1 ? "" : S.substring(leftIndex, rightIndex+1);
    }

    public static void main(String[] args) {
        String str1 = "a";
        String str2 = "a";
        MinWindow minWindow = new MinWindow();
        System.out.println(minWindow.minWindow(str1, str2));
    }
}
